home *** CD-ROM | disk | FTP | other *** search
/ Inter.Net 55-1 / Inter.Net 55-1.iso / CBuilder / Setup / BCB / data.z / queue.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-02-09  |  9.1 KB  |  275 lines
  1. #ifndef __STD_QUEUE__
  2. #define __STD_QUEUE__
  3. #pragma option push -b -a4 -Vx- -Ve- -w-inl -w-aus -w-sig
  4.  
  5. /***************************************************************************
  6.  *
  7.  * queue - declarations for the Standard Library queue classes
  8.  *
  9.  * $Id: queue,v 1.33 1996/09/03 23:14:41 smithey Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED *
  29.  * The software and information contained herein are proprietary to, and
  30.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  31.  * intends to preserve as trade secrets such software and information.
  32.  * This software is furnished pursuant to a written license agreement and
  33.  * may be used, copied, transmitted, and stored only in accordance with
  34.  * the terms of such license and with the inclusion of the above copyright
  35.  * notice.  This software and information or any other copies thereof may
  36.  * not be provided or otherwise made available to any other person.
  37.  *
  38.  * Notwithstanding any other lease or license that may pertain to, or
  39.  * accompany the delivery of, this computer software and information, the
  40.  * rights of the Government regarding its use, reproduction and disclosure
  41.  * are as set forth in Section 52.227-19 of the FARS Computer
  42.  * Software-Restricted Rights clause.
  43.  * 
  44.  * Use, duplication, or disclosure by the Government is subject to
  45.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  46.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  47.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  48.  * P.O. Box 2328, Corvallis, Oregon 97339.
  49.  *
  50.  * This computer software and information is distributed with "restricted
  51.  * rights."  Use, duplication or disclosure is subject to restrictions as
  52.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  53.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  54.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  55.  * then the "Alternate III" clause applies.
  56.  *
  57.  **************************************************************************/
  58.  
  59. #include <stdcomp.h>
  60.  
  61. #ifndef _RWSTD_HEADER_REQUIRES_HPP
  62. #include <algorithm>
  63. #include <functional>
  64. #include <deque>
  65. #include <vector>
  66. #else
  67. #include <algorithm.hpp>
  68. #include <functional.hpp>
  69. #include <deque.hpp>
  70. #include <vector.hpp>
  71. #endif
  72.  
  73. #ifndef _RWSTD_NO_NAMESPACE
  74. namespace std {
  75. #endif
  76.  
  77. #ifdef _RWSTD_NO_UNDEFINED_FRIEND
  78. template <class T, class Container> class queue;
  79.  
  80. template <class T, class Container>
  81. inline bool operator== (const queue<T,Container>& x, 
  82.                  const queue<T,Container>& y);
  83.  
  84. template <class T, class Container>
  85. inline bool operator< (const queue<T,Container>& x, 
  86.                 const queue<T,Container>& y);
  87. #endif
  88.  
  89. #ifndef _RWSTD_NO_COMPLEX_DEFAULT_TEMPLATES
  90. template <class T, class Container = deque<T> >
  91. #else
  92. template <class T, class Container>
  93. #endif  
  94. class queue
  95. {
  96.     friend bool operator== (const queue<T,Container>& x,
  97.                             const queue<T,Container>& y);
  98.     friend bool operator<  (const queue<T,Container>& x,
  99.                             const queue<T,Container>& y);
  100.   public:
  101.  
  102.     typedef _TYPENAME Container::value_type value_type;
  103.     typedef _TYPENAME Container::size_type  size_type;
  104.     typedef _TYPENAME Container::allocator_type       allocator_type;
  105.  
  106.   protected:
  107.  
  108.     Container c;
  109.  
  110.   public:
  111.     _EXPLICIT queue(const allocator_type& alloc _RWSTD_DEFAULT_ARG(allocator_type())) : c(alloc)
  112.     { ; }
  113.  
  114. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  115.     queue(void) : c(allocator_type())
  116.     { ; }
  117. #endif
  118.  
  119.     allocator_type get_allocator() const
  120.     { 
  121.       return c.get_allocator(); 
  122.     }
  123.  
  124.     bool                  empty () const              { return c.empty(); }
  125.     size_type             size  () const              { return c.size();  }
  126.     value_type&           front ()                    { return c.front(); }
  127.     const value_type&     front () const              { return c.front(); }
  128.     value_type&           back  ()                    { return c.back();  }
  129.     const value_type&     back  () const              { return c.back();  }
  130.     void                  push  (const value_type& x) { c.push_back(x);   }
  131.     void                  pop   ()                    { c.pop_front();    }
  132.  
  133. };
  134.  
  135. template <class T, class Container>
  136. inline bool operator== (const queue<T,Container>& x, 
  137.                         const queue<T,Container>& y)
  138. {
  139.     return x.c == y.c;
  140. }
  141.  
  142. template <class T, class Container>
  143. inline bool operator< (const queue<T,Container>& x, 
  144.                        const queue<T,Container>& y)
  145. {
  146.     return x.c < y.c;
  147. }
  148.  
  149. template <class T, class Container>
  150. inline bool operator!= (const queue<T,Container>& x, 
  151.                         const queue<T,Container>& y)
  152. {
  153.     return !(x == y);
  154. }
  155.  
  156. template <class T, class Container>
  157. inline bool operator> (const queue<T,Container>& x, 
  158.                        const queue<T,Container>& y)
  159. {
  160.     return y < x;
  161. }
  162.  
  163. template <class T, class Container>
  164. inline bool operator>= (const queue<T,Container>& x, 
  165.                         const queue<T,Container>& y)
  166. {
  167.     return !(x < y);
  168. }
  169.  
  170. template <class T, class Container>
  171. inline bool operator<= (const queue<T,Container>& x, 
  172.                         const queue<T,Container>& y)
  173. {
  174.     return !(y <  x);
  175. }
  176.  
  177. #ifndef _RWSTD_NO_COMPLEX_DEFAULT_TEMPLATES
  178. template<class T, class Container = vector<T>,
  179.          class Compare = less<_TYPENAME Container::value_type> >
  180. #else
  181. template <class T, class Container, class Compare> 
  182. #endif
  183. class priority_queue
  184. {
  185.   public:
  186.  
  187.     typedef _TYPENAME Container::value_type value_type;
  188.     typedef _TYPENAME Container::size_type  size_type;
  189.     typedef _TYPENAME Container::allocator_type       allocator_type;
  190.  
  191.   protected:
  192.  
  193.     Container c;
  194.     Compare   _RWSTD_COMP;
  195.  
  196.   public:
  197.  
  198.     _EXPLICIT priority_queue (const Compare& x _RWSTD_DEFAULT_ARG(Compare()),
  199.                              const allocator_type& alloc _RWSTD_DEFAULT_ARG(allocator_type())) 
  200.            : c(alloc), _RWSTD_COMP(x) 
  201.     { ; }
  202.  
  203. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  204.     priority_queue (void)
  205.            : c(allocator_type()), _RWSTD_COMP(Compare()) 
  206.     { ; }
  207.  
  208.     _EXPLICIT priority_queue (const Compare& x _RWSTD_DEFAULT_ARG(Compare()))
  209.            : c(allocator_type()), _RWSTD_COMP(x) 
  210.     { ; }
  211. #endif
  212.  
  213.     allocator_type get_allocator() const
  214.     { 
  215.       return c.get_allocator(); 
  216.     }
  217.  
  218. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  219.     template <class InputIterator>
  220.     priority_queue (InputIterator first, InputIterator last, 
  221.                     const Compare& x = Compare(),
  222.                     const allocator_type& alloc = allocator_type()) 
  223.           : c(first, last,alloc), _RWSTD_COMP(x) 
  224.     {
  225.         make_heap(c.begin(), c.end(), _RWSTD_COMP);
  226.     }
  227. #else
  228.     priority_queue (_TYPENAME Container::const_iterator first,
  229.                     _TYPENAME Container::const_iterator last,
  230.                     const Compare& x _RWSTD_DEFAULT_ARG(Compare()),
  231.                     const allocator_type& alloc _RWSTD_DEFAULT_ARG(allocator_type())) 
  232.           : c(first, last,alloc), _RWSTD_COMP(x)
  233.     {
  234.         make_heap(c.begin(), c.end(), _RWSTD_COMP);
  235.     }
  236. #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
  237.     priority_queue (_TYPENAME Container::const_iterator first,
  238.                     _TYPENAME Container::const_iterator last,
  239.                     const Compare& x _RWSTD_DEFAULT_ARG(Compare()))
  240.           : c(first, last,allocator_type()), _RWSTD_COMP(x)
  241.     {
  242.         make_heap(c.begin(), c.end(), _RWSTD_COMP);
  243.     }
  244.  
  245.     priority_queue (_TYPENAME Container::const_iterator first,
  246.                     _TYPENAME Container::const_iterator last)
  247.           : c(first, last,allocator_type()), _RWSTD_COMP(Compare())
  248.     {
  249.         make_heap(c.begin(), c.end(), _RWSTD_COMP);
  250.     }
  251. #endif
  252. #endif
  253.     
  254.     bool                  empty () const { return c.empty(); }
  255.     size_type             size  () const { return c.size();  }
  256.     value_type&           top   ()       { return c.front(); }
  257.     const value_type&     top   () const { return c.front(); }
  258.  
  259.     void push (const value_type& x)
  260.     { 
  261.         c.push_back(x); push_heap(c.begin(), c.end(), _RWSTD_COMP);
  262.     }
  263.     void pop ()
  264.     {
  265.         pop_heap(c.begin(), c.end(), _RWSTD_COMP); c.pop_back(); 
  266.     }
  267. };
  268.  
  269. #ifndef _RWSTD_NO_NAMESPACE
  270. }
  271. #endif
  272.  
  273. #pragma option pop
  274. #endif /* __STD_QUEUE__ */
  275.